# 变体一: 数组中存在相同的元素，寻找第一个相同的元素
def binary_change01(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        elif arr[mid] > target:
            high = mid - 1
        else:
            if mid == 0 or arr[mid - 1] != target:
                return mid
            else:
                high = mid - 1
    return -1


# 变体二: 数组中存在相同的元素，寻找第一个相同的元素
def binary_change02(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        elif arr[mid] > target:
            high = mid - 1
        else:
            if mid == high or arr[mid + 1] != target:
                return mid
            else:
                low = mid + 1
    return -1


# 变体三: 元素不重复，寻找第一个大于等于target的值
def binary_change03(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < target:
            high = mid - 1
        else:
            if mid == 0 or arr[mid - 1] < target:
                return mid
            else:
                low = mid + 1
    return -1


# 变体四: 元素不重复，寻找最后一个小于等于target的值
def binary_change04(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] > target:
            high = mid - 1
        else:
            if mid == high or arr[mid + 1] > target:
                return mid
            else:
                low = mid + 1
    return -1


if __name__ == '__main__':
    array = [2, 3, 5, 9, 22, 29, 35, 67]
    print(binary_change04(array, 23))
